package heap

import (
	"fmt"
	"math/rand"
	"time"
)

type Heap struct {
	count    int
	data     [] int
	capacity int
}

func instance(capacity int) *Heap {

	return &Heap{count: 0, capacity: capacity, data: make([]int, capacity+1)}
}

func (this *Heap) insert(data int) {

	if this.count >= this.capacity {
		return
	}

	this.count++
	this.data[this.count] = data
	i := this.count
	for i/2 > 0 && this.data[i] < this.data[i/2] { // 自下往上堆化
		//交换下标为i和i/2的两个元素
		this.data[i], this.data[i/2] = this.data[i/2], this.data[i]
		i = i / 2
	}

}

func (this *Heap) get() int {

	if this.count <= 0 {
		return 0
	}

	return this.data[1]
}

func (this *Heap) remove(i int) {

	if this.count == 0 || this.capacity-i < 0 {
		return
	}

	//temp := this.data[i]
	this.data[i] = this.data[this.count]

	for {
		maxPos := i
		if i*2 <= this.count && this.data[i] > this.data[i*2] {
			maxPos = i * 2
		}
		if i*2+1 <= this.count && this.data[maxPos] > this.data[i*2+1] {
			maxPos = i*2 + 1
		}

		if maxPos == i {
			this.data[this.count] = 0
			this.count--
			break
		}

		this.data[i], this.data[maxPos] = this.data[maxPos], this.data[i]
		i = maxPos
	}
}

func main() {

	heap := instance(3)

	arr := make([]int, 10)

	rand.Seed(time.Now().UnixNano())

	for i := 0; i < 10; i++ {
		intn := rand.Intn(1000)
		arr[i] = intn
		//heap.insert(intn)
	}

	for i := 0; i < len(arr); i++ {

		data := heap.get()

		if arr[i] > data {

			if heap.count == heap.capacity {
				heap.remove(1)
			}

			heap.insert(arr[i])
		}
	}

	fmt.Println(arr)

	fmt.Println(heap)


}
